#include "rbtree_queue.h"


static inline void rbtree_queue_node_free(rbqueue_node_ref_t q_node)
{
    if (q_node != NULL) {
        if (q_node->key != NULL){
            g_free(q_node->key);
            q_node->key = NULL;
        }
        g_free(q_node);
        q_node = NULL;
    }
}

int rbtree_queue_init(rbtree_queue_ref_t queue_root)
{
    memset(queue_root, 0 , sizeof(rbtree_queue_t));
    locker_create(&queue_root->lock);
    queue_root->root_node.rb_node=NULL;
    return 0;
}

int rbtree_queue_deinit(rbtree_queue_ref_t queue_root)
{
    rbqueue_node_t *p_queue_node;

    while (!RB_QUEUE_EMPTY_ROOT(queue_root)) {
        p_queue_node = rbtree_queue_first_node(queue_root);
        rb_erase(&p_queue_node->node, &queue_root->root_node);
        rbtree_queue_node_free(p_queue_node);
    }
    queue_root->size = 0;
    locker_destroy(&queue_root->lock);

    return 0;
}

int rbtree_queue_insert(rbtree_queue_ref_t queue_root,
    char *in_key,void *data)
{
    struct rb_root *root = &queue_root->root_node;
    struct rb_node **_new = &(root->rb_node), *parent = NULL;
    rbqueue_node_t *p_queue_node =g_malloc(sizeof(rbqueue_node_t));

    memset(p_queue_node, 0 , sizeof(rbqueue_node_t));
    p_queue_node->key = (char*)g_malloc((strlen(in_key)+1)*sizeof(char));
    strcpy(p_queue_node->key, in_key);
    p_queue_node->priv_data = data;

    /* Figure out where to put new node */
    while (*_new) {
        rbqueue_node_t *_this = rb_entry(*_new, rbqueue_node_t, node);
        int result = strcmp(p_queue_node->key, _this->key);
    
        parent = *_new;
        if (result < 0){
            _new = &((*_new)->rb_left);
        }else if (result > 0){
            _new = &((*_new)->rb_right);
        }else{
            rbtree_queue_node_free(p_queue_node);
            return false;
        }
    }

    /* Add new node and rebalance tree. */
    rb_link_node(&p_queue_node->node, parent, _new);
    rb_insert_color(&p_queue_node->node, root);
    queue_root->size++;
    return true;
}

rbqueue_node_t *rbtree_queue_search_node(rbtree_queue_ref_t queue_root,
     char *in_key)
{
    struct rb_node *tmp_node = queue_root->root_node.rb_node;

    while (tmp_node) {
        rbqueue_node_t *_this = rb_entry(tmp_node, rbqueue_node_t, node);
        int result = strcmp(in_key, _this->key);
        if (result < 0)
            tmp_node = tmp_node->rb_left;
        else if (result > 0)
            tmp_node = tmp_node->rb_right;
        else
            return _this;//return node
    }
    return NULL;
}
void *rbtree_queue_search(rbtree_queue_ref_t queue_root, char *in_key)
{
    rbqueue_node_t *p_queue_node = rbtree_queue_search_node(queue_root,in_key);
    if(NULL == p_queue_node){
        return NULL;
    }else{
        return p_queue_node->priv_data;
    }
}

int rbtree_queue_erase(rbtree_queue_ref_t queue_root, char *in_key)
{
    rbqueue_node_t *p_queue_node = rbtree_queue_search_node(queue_root,in_key);
    if(NULL == p_queue_node){
        return -1;
    }else{
        rb_erase(&p_queue_node->node, &queue_root->root_node);
        rbtree_queue_node_free(p_queue_node);
        queue_root->size--;
    }
    return 0;
}

rbqueue_node_t *rbtree_queue_first_node(rbtree_queue_ref_t queue_root)
{
    struct rb_node *first = rb_first(&queue_root->root_node);
    if(first){
        return (rbqueue_node_t *)(rb_entry(first, rbqueue_node_t, node));
    }else{
        return NULL;
    }
    return NULL;//for compile warning
}
rbqueue_node_t *rbtree_queue_next_node(rbqueue_node_t *p_queue_node)
{
    struct rb_node *next =  rb_next(&p_queue_node->node);
    if(next){
        return (rbqueue_node_t *)(rb_entry(next, rbqueue_node_t, node));
    }else{
        return NULL;
    }
    return NULL;//for compile warning
}
rbqueue_node_t *rbtree_queue_prev_node(rbqueue_node_t *p_queue_node)
{
    struct rb_node *prev =  rb_prev(&p_queue_node->node);
    if(prev){
        return (rbqueue_node_t *)(rb_entry(prev, rbqueue_node_t, node));
    }else{
        return NULL;
    }
    return NULL;//for compile warning
}

rbqueue_node_t *rbtree_queue_last_node(rbtree_queue_ref_t queue_root)
{
    struct rb_node *last = rb_last(&queue_root->root_node);
    if(last){
        return (rbqueue_node_t *)rb_entry(last, struct __rbqueue_node_t, node);
    }else{
        return NULL;
    }
    return NULL;//for compile warning
}